Anomaly Detection

In data analysis, anomaly detection (also referred to as outlier detection and sometimes as novelty detection) is generally understood to be the identification of rare items, events or observations which deviate significantly from the majority of the data and do not conform to a well defined notion of normal behaviour. Such examples may arouse suspicions of being generated by a different mechanism, or appear inconsistent with the remainder of that set of data.

Anomaly detection finds application in many domains including cyber security, medicine, machine vision, statistics, neuroscience, law enforcement and financial fraud to name only a few. Anomalies were initially searched for clear rejection or omission from the data to aid statistical analysis, for example to compute the mean or standard deviation. They were also removed to better predictions from models such as linear regression, and more recently their removal aids the performance of machine learning algorithms. However, in many applications anomalies themselves are of interest and are the observations most desirous in the entire data set, which need to be identified and separated from noise or irrelevant outliers.

Three broad categories of anomaly detection techniques exist. Supervised anomaly detection techniques require a data set that has been labeled as "normal" and "abnormal" and involves training a classifier. However, this approach is rarely used in anomaly detection due to the general unavailability of labelled data and the inherent unbalanced nature of the classes. Semi-supervised anomaly detection techniques assume that some portion of the data is labelled. This may be any combination of the normal or anomalous data, but more often than not the techniques construct a model representing normal behavior from a given ''normal'' training data set, and then test the likelihood of a test instance to be generated by the model. Unsupervised anomaly detection techniques assume the data is unlabelled and are by far the most commonly used due to their wider and relevant application.

Definition

Many attempts have been made in the statistical and computer science communities to define an anomaly. The most prevalent ones include:

* An outlier is an observation which deviates so much from the other observations as to arouse suspicions that it was generated by a different mechanism.
* Anomalies are instances or collections of data that occur very rarely in the data set and whose features differ significantly from most of the data.
* An outlier is an observation (or subset of observations) which appears to be inconsistent with the remainder of that set of data.
* An anomaly is a point or collection of points that is relatively distant from other points in multi-dimensional space of features.
* Anomalies are patterns in data that do not conform to a well defined notion of normal behaviour.
* Let T be observations from a univariate Gaussian distribution and O a point from T. Then the z-score for O is greater than a pre-selected threshold if and only if O is an outlier.

Applications

Anomaly detection is applicable in a very large number and variety of domains, and is an important subarea of unsupervised machine learning. As such it has applications in cyber-security intrusion detection, fraud detection, fault detection, system health monitoring, event detection in sensor networks, detecting ecosystem disturbances, defect detection in images using machine vision, medical diagnosis and law enforcement.

Anomaly detection was proposed for intrusion detection systems (IDS) by Dorothy Denning in 1986. Anomaly detection for IDS is normally accomplished with thresholds and statistics, but can also be done with soft computing, and inductive learning. Types of statistics proposed by 1999 included profiles of users, workstations, networks, remote hosts, groups of users, and programs based on frequencies, means, variances, covariances, and standard deviations. The counterpart of anomaly detection in intrusion detection is misuse detection.

It is often used in preprocessing to remove anomalous data from the dataset. This is done for a number of reasons. Statistics of data such as the mean and standard deviation are more accurate after the removal of anomalies, and the visualisation of data can also be improved. In supervised learning, removing the anomalous data from the dataset often results in a statistically significant increase in accuracy. Anomalies are also often the most important observations in the data to be found such as in intrusion detection or detecting abnormalities in medical images.

Popular techniques

Many anomaly detection techniques have been proposed in literature. Some of the popular techniques are:

* Statistical ( Z-score, Tukey's range test and Grubbs's test)
* Density-based techniques (k-nearest neighbor, local outlier factor, isolation forests, and many more variations of this concept)
* Subspace-, correlation-based and tensor-based outlier detection for high-dimensional data
* One-class support vector machines
* Replicator neural networks, autoencoders, variational autoencoders, long short-term memory neural networks
* Bayesian networks
* Hidden Markov models (HMMs)
* Minimum Covariance Determinant
* Clustering: Cluster analysis-based outlier detection
* Deviations from association rules and frequent itemsets
* Fuzzy logic-based outlier detection
* Ensemble techniques, using feature bagging, score normalization and different sources of diversity

The performance of methods depends on the data set and parameters, and methods have little systematic advantages over another when compared across many data sets and parameters.

Software

* ELKI is an open-source Java data mining toolkit that contains several anomaly detection algorithms, as well as index acceleration for them.
*PyOD is an open-source Python library developed specifically for anomaly detection.
* scikit-learn is an open-source Python library that has built functionality to provide unsupervised anomaly detection.
* Wolfram Mathematica provides functionality for unsupervised anomaly detection across multiple data types
Mathematica documentation

Datasets

Anomaly detection benchmark data repository
with carefully chosen data sets of the Ludwig-Maximilians-Universität München
Mirror
at University of São Paulo.

ODDS
– ODDS: A large collection of publicly available outlier detection datasets with ground truth in different domains.

Unsupervised Anomaly Detection Benchmark
at Harvard Dataverse: Datasets for Unsupervised Anomaly Detection with ground truth.

KMASH Data Repository
at Research Data Australia having more than 12,000 anomaly detection datasets with ground truth.

See also

* Change detection
* Statistical process control
* Novelty detection
* Hierarchical temporal memory

References

{{Authority control

Data mining
Machine learning
Data security
Statistical outliers